Search results for "Hamiltona cikls"

Planāra grafa dualitātes īpašības

2016

Maģistra darbā padziļināti aplūkoti vairāki jautājumi par atsevišķa veida ciklu eksistenci grafā. Tā kā literatūrā nav pietiekami plaši izpētīta Hamiltona cikla un Eilera cikla saistība ar duālo grafu, tad darba ietvaros tika formulētas teorēmas un veikti secinājumi par šo tēmu. Darbā apkopotās un formulētās sakarības izmantotas, lai izveidotu un analizētu algoritmus Hamiltona cikla eksistences novērtēšanai. Nozīmīgākās darbā formulētās sakarības ir Grinberga teorēma duālajam grafam, teorēmas par Hamiltona cikla un Eilera cikla eksistenci vienlaikus gan primārajā, gan duālajā grafā, kā arī secinājums par Hamiltona cikla eksistenci atkarībā no duālā grafa minimālās atdalošo šķautņu kopas. Īp…